package com.arrays;

import java.util.HashMap;

public class MinimumWindowSubstring0125_76 {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> hs = new HashMap<>();
        HashMap<Character, Integer> ht = new HashMap<>();

        for (int i = 0; i < t.length(); i++) {
            ht.put(t.charAt(i),ht.getOrDefault(t.charAt(i),0)+1);
        }

        String ans = "";
        int len = Integer.MAX_VALUE; //用于跟踪最短的满足条件的子串的长度
        int cnt=0;// cnt维护的是s字符串[j,i]区间中满足t字符串的元素的个数，记录相对应字符的总数。
        //区间[j,i]表示当前滑动窗口
        for (int i = 0,j = 0; i < s.length(); i++) {
            hs.put(s.charAt(i),hs.getOrDefault(s.charAt(i),0)+1);

            if(ht.containsKey(s.charAt(i)) && ht.get(s.charAt(i)) >= hs.get(s.charAt(i))){
                cnt++;
            }
            while (j < i && (!ht.containsKey(s.charAt(j)) || hs.get(s.charAt(j)) > ht.get(s.charAt(j)))){
                hs.put(s.charAt(j), hs.get(s.charAt(j)) -1);
                j++;
            }

            if(cnt == t.length()&& i-j+1 <len){
                len = i-j+1;
                ans = s.substring(j,i+1);
            }
        }
        return ans;
    }
}
